package jjn.round2;

/**
 * @author Jiang Jining
 * @since 2023-06-19 22:37
 */
public class LeetCode1262_GreatestSumDividedByThree {
    public int maxSumDivThree(int[] nums) {
        int[][] dp = new int[nums.length + 1][3];
        dp[0][0] = 0;
        dp[0][1] = Integer.MIN_VALUE;
        dp[0][2] = Integer.MIN_VALUE;
        for (int i = 1; i <= nums.length; i++) {
            int num = nums[i - 1];
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j - num % 3 + 3) % 3] + num);
            }
        }
        return dp[nums.length][0];
    }
}
